import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 25397
 * Date: 2021-11-11
 * Time: 8:27
 */
class ListNode{//ListNode代表一个节点
    public int val;//每个节点的值
    public ListNode next;//next存放下一个“节点”地址，next也应该是节点类型
    //有点类似“人类型”Person p=new Person()，p里面存放new的对象的地址
    //然后p可以引用人这个类型里的东西如p.age
    //next是一个引用类型，默认为null，//引用数据类型：数组、类、接口默认值null
    public ListNode(int val){
        this.val=val;
    }
}
public class myLinkedList {
    //链表由一个个叫作节点的东西组成
    //每个节点有val：数据域，next：下一个节点的地址
    //链表有2^3=8种
    //单向、双向
    //带头、不带头
    //循环、非循环
    //考试面试只考“单向、不带头、非循环”与“双向、不带头、非循环”
    //本文主要介绍单向不带头非循环
    public ListNode head;//链表的头引用，head永远用于存储链表第一个节点的地址
    //这里为什么类型是ListNode？——和类里面 public ListNode next;一个道理
    //为什么不定义在class ListNode里面？因为head是链表的头，不是节点的头，节点里面只有两个——val和next

    public void createList(){
        ListNode listNode1=new ListNode(12);
        ListNode listNode2=new ListNode(23);
        ListNode listNode3=new ListNode(34);
        ListNode listNode4=new ListNode(45);
        ListNode listNode5=new ListNode(56);
        //到这里我们5个节点创建好了，但它们之间没有联系
        //每个节点里面的next都是null
        listNode1.next=listNode2;//lisNode里面存储了new的对象的地址，我们通过next来获得下一个节点的地址
        listNode2.next=listNode3;
        listNode3.next=listNode4;
        listNode4.next=listNode5;
        //listNode5=null;//这句代码可以不写，因为引用数据类型：数组、类、接口默认值null
        //到这里，5个节点就连起来了
        this.head=listNode1;//使得head指向第一个节点
    }

    public void createList2(){//测试用，实际效果和createList一样，只不过少几个节点
        ListNode listNode1=new ListNode(13);
        ListNode listNode2=new ListNode(24);
        ListNode listNode3=new ListNode(30);
        listNode1.next=listNode2;
        listNode2.next=listNode3;
        listNode3.next=null;
        this.head=listNode1;
    }

    public void createList3(){
        ListNode listNode1=new ListNode(12);
        ListNode listNode2=new ListNode(2);
        ListNode listNode3=new ListNode(34);
        ListNode listNode4=new ListNode(4);
        ListNode listNode5=new ListNode(56);
        //到这里我们5个节点创建好了，但它们之间没有联系
        //每个节点里面的next都是null
        listNode1.next=listNode2;//lisNode里面存储了new的对象的地址，我们通过next来获得下一个节点的地址
        listNode2.next=listNode3;
        listNode3.next=listNode4;
        listNode4.next=listNode5;
        //listNode5=null;//这句代码可以不写，因为引用数据类型：数组、类、接口默认值null
        //到这里，5个节点就连起来了
        this.head=listNode1;//使得head指向第一个节点
    }

    public void createList4(){
        ListNode listNode1=new ListNode(1);
        ListNode listNode2=new ListNode(2);
        ListNode listNode3=new ListNode(3);
        ListNode listNode4=new ListNode(2);
        ListNode listNode5=new ListNode(1);
        //到这里我们5个节点创建好了，但它们之间没有联系
        //每个节点里面的next都是null
        listNode1.next=listNode2;//lisNode里面存储了new的对象的地址，我们通过next来获得下一个节点的地址
        listNode2.next=listNode3;
        listNode3.next=listNode4;
        listNode4.next=listNode5;
        //listNode5=null;//这句代码可以不写，因为引用数据类型：数组、类、接口默认值null
        //到这里，5个节点就连起来了
        this.head=listNode1;//使得head指向第一个节点
    }

    public void createList5(){
        ListNode listNode1=new ListNode(1);
        ListNode listNode2=new ListNode(2);
        ListNode listNode4=new ListNode(2);
        ListNode listNode5=new ListNode(1);
        listNode1.next=listNode2;
        listNode2.next= listNode4;
        listNode4.next=listNode5;
        this.head=listNode1;
    }

    public void createList6(){
        ListNode listNode1=new ListNode(1);
        ListNode listNode2=new ListNode(3);
        ListNode listNode4=new ListNode(2);
        ListNode listNode5=new ListNode(1);
        listNode1.next=listNode2;
        listNode2.next= listNode4;
        listNode4.next=listNode5;
        this.head=listNode1;
    }
    //遍历（打印整个链表）
    public void display(){
        ListNode cur=this.head;
        //这里创建一个临时变量是为了head仍指向头节点，防止遍历完后head指向null了，那样head就是一次性使用品了，后续也无法继续遍历
        while(cur!=null){//这里为什么不是cur.next！=null
            //比如链表里有1     2     3     4    5
            //          &2   &3    &4     &5   null
            //                                 cur.next到5的时候就结束了，5不会被打印
            //                                 cur到5，打印完5，cur=cur.next=null，结束打印（正确）
            System.out.print(cur.val+" ");
            cur=cur.next;
        }
        System.out.println();
    }

    //判断一个数key是否在链表中
    public boolean contain(int key){
        ListNode cur=this.head;
        while(cur!=null){
            if(cur.val==key){
                return true;
            }
            cur=cur.next;
        }
        return false;
    }

    //计算链表长度
    public int size(){
        int count=0;
        ListNode cur=this.head;
        while(cur!=null){
            count++;
            cur=cur.next;
        }
        return count;
    }

    //头插法
    public void addFirst(int data){
        ListNode node=new ListNode(data);
        //法一
        /*if(this.head==null){//原先链表里无节点
            this.head=node;
        }
        else{
            node.next=head;
            head=node;
        }*/

        //法二
        node.next=head;
        head=node;//对于原先链表中有无节点都适用
    }

    //尾插法
    public void addLast(int data){
        ListNode node=new ListNode(data);
        if(this.head==null){//原先链表里面没有
            this.head=node;
        }
        else{
            ListNode cur=this.head;
            while(cur.next!=null){
                cur=cur.next;
            }//完成循环cur指向尾节点
            cur.next=node;
        }
    }

    //找到index-1位置的节点的地址（节点下标从0开始计算）
    //比如我传参过来是2，我是想找第二个节点地址，对应的index-1是1
    //节点 1   2   3   4   5
    //    cur
    //       cur
    //进行index-1次循环即可
    public ListNode findIndex(int index){
        ListNode cur=this.head;
        while(index-1!=0){
            cur=cur.next;
            index--;
        }
        return cur;
    }

    //任意位置插入节点，第一个数据节点下标为0
    public void addIndex(int index,int key){//在第index位置插入节点，节点里数据为key
        if(index<0||index>size()){
            System.out.println("index位置不合法");
            return;
        }
        if(index==0){
            addFirst(key);
            return;
        }
        if(index==size()){
            addLast(key);
            return;
        }
        ListNode cur=this.findIndex(index);
        ListNode node=new ListNode(key);
        node.next=cur.next;
        cur.next=node;
    }

    //删除第一次出现的数据key
    public void deleteIndex(int key){
        if(this.head==null){
            System.out.println("链表为空，无法进行删除");
        }
        ListNode cur=this.head;
        if(this.head.val==key){
            this.head=this.head.next;
            return;
        }
        while(cur.next!=null){
            if(cur.next.val==key){
                cur.next=cur.next.next;
               return;
            }
            cur=cur.next;
        }
        if(cur.next==null){
            System.out.println("未找到要删除的元素");
        }
    }

    //遍历链表一遍，删除链表中所有等于key的值——面试题难度
    public void deleteAllIndex(int key){
        if(this.head==null){
            System.out.println("链表为空，无法进行删除操作");
            return;
        }
        ListNode prev=this.head;//作为cur的前驱
        ListNode cur=this.head.next;
        while(cur!=null){
            if(cur.val==key){
                prev.next=cur.next;
                cur=cur.next;
            }
            else{
                prev=cur;
                cur=cur.next;
            }
        }
        //到这里，除了头结点（如果头结点数据==key），其他等于key的值都删完了
        if(this.head.val==key){
            this.head=this.head.next;
        }
    }

    //链表的逆置，比如原链表1 2 3 4 5，逆置后变为5 4 3 2 1
    //步骤：
    //1 2 3 4 5
    //2 1 3 4 5
    //3 2 1 4 5
    //4 3 2 1 5
    //5 4 3 2 1
    public void nz(){
        if(this.head==null){
            System.out.println("链表中无元素");
            return;
        }
        ListNode prev=null;
        ListNode cur=this.head;
        while(cur!=null){
            ListNode curNext=cur.next;
            cur.next=prev;
            prev=cur;
            cur=curNext;
        }
        //因为逆置后head仍指向原先的第一个节点（逆置后原先第一个节点下一个指向变为null），
        // 所以我们原先的display函数不能用了，否则只能打印一个元素，我们下面重写一个打印函数
        ListNode cur2=prev;
        while(cur2!=null){
            System.out.print(cur2.val+" ");
            cur2=cur2.next;
        }
        System.out.println();
    }
    //给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点
    //比如1 2 3 4 5，给定1节点，要求返回3节点
    //或者1 2 3 4，给定1节点，要求返回2节点
    //如果是正常题目，你可以自己先遍历一下链表，得到链表长度n，然后头节点走n/2步返回中间节点
    //但如果是面试题，只允许遍历一遍得到，我们这里就设计到快慢指针的问题
    //我们正常遍历是走完链表，但我们现在只需要中间的元素，我们可以定义一个fast和slow，
    //fast走的速度是slow的2倍，同一次遍历，fast走完整个长度，slow正好走到中间节点
    public ListNode middleNode(){
        if(head==null){
            return null;
        }
        ListNode fast=head;
        ListNode slow=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow =slow.next;
        }
        return slow;
    }

    //输入一个链表，输出该链表中倒数第k个结点
    //和上题一样，也是快慢指针的问题
    //输出该链表倒数第k个节点，也就是或慢指针走到length-k，快指针走完了k
    //快指针比慢指针多走k-1步
    //比如1 2 3 4 5 现要输出该链表倒数第2个节点
    //   s
    //     s
    //       s
    //         s  f
    //慢指针从1到4共走三步，也就是length-k=5-2=3，快指针从1到5共4步，也就是length-1=5-1=4
    //快指针比慢指针多走(length-1)-(length-k)=k-1步
    public ListNode FindKthToTail(ListNode head,int k){
        if(k<=0||k>size()){
            System.out.println("k值输入错误，请重新输入");
            return null;
        }
        else{
            ListNode fast=head;
            ListNode slow=head;
            int i=0;
            for(i=0;i<size();i++){
                if(i<k-1){
                    fast=fast.next;
                }
                else if(k-1<=i&&i<size()-1){//这里容易混淆的是，我们下标的从0开始，但是size（）是从1开始计算
                    //这里i<size()-1是因为fast到size()就不用往下走了
                    //比如size()是5,我们现在求倒数第2个数（k=2）
                    //已经走了k-1=1步，也就是到了2这个节点，再往下走三步即可
                    //k-1=1<i<5-1=4
                    //1  2  3  4  5
                    //f
                    //   f
                    //      f
                    //         f
                    //            f
                    fast=fast.next;
                    slow=slow.next;//当然，如果你觉得这样写很容易出问题
                    //你可以这样写循环while(fast.next!=null){...}，这样fast到最后一个节点就自动停下了
                }
            }
           return slow;
        }
    }


    //编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前（不改变原有链表顺序）
    //比如：现有链表12  3  34  5  56
    //给定10，让小于10的排在前面，大于10的排在后面
    //效果如下：3  5  12  34  56
    //解题思路：创建两个链表，1个存放小于x的数，另一个存放大于x的数，然后把两个链表连起来即可
    public ListNode partition(int x){
        ListNode bs=null;//before start用于标记x前面的链表头结点
        ListNode be=null;//before end用于标记x前面的链表尾部节点
        ListNode as=null;//after start
        ListNode ae=null;
        ListNode cur=head;
        while(cur!=null){
            if(cur.val<x){
                if(bs==null){
                    bs=cur;
                    be=cur;
                }
                else{
                    be.next=cur;
                    be=be.next;
                }
            }
            else{
                if(as==null){
                    as=cur;
                    ae=cur;
                }
                else{
                    ae.next=cur;
                    ae=ae.next;
                }
            }
            cur=cur.next;
        }
        if(bs==null){//原先链表里没有数比x小
            return as;
        }
        be.next=as;
        if(as!=null){//如果原先没有比x大的，as就是null，直接打印第一个链表即可
            ae.next=null;
        }
        return bs;
    }


    //在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针
    public ListNode deleteDuplication(){
        ListNode cur=head;
        ListNode newHead=new ListNode(-1);
        ListNode tmp=newHead;
        while(cur!=null){
            if(cur.next!=null&&cur.val==cur.next.val){
                while(cur.next!=null&&cur.val==cur.next.val){
                    cur=cur.next;
                }
                cur=cur.next;
            }
            else{
                tmp.next=cur;
                tmp=tmp.next;
                cur=cur.next;
            }
        }
        tmp.next=null;
        return newHead.next;
    }

    //链表的回文结构
    //回文：正着读反着读都一样，比如1221 12321
    //对于一个链表，请设计一个时间复杂度为O（n），空间复杂度为O（1）的算法，判断其是否为回文结构
    //给定一个链表头指针A，请返回一个bool值，判断是否为回文结构
    //eg:1->2->2->1 返回true
    //思路，这里也是快慢指针，快慢指针同时走，快指针（F）先走到最后位置（后续不用再走了），这时慢指针到中间位置，
    // 慢指针（S）往后走，边走，变将后面的指向逆置
    //这里往回走为什么要逆置，因为是单链表，你不逆置无法从后往前
    //比如1->2->3->4->3->2->1
    //            S
    //   1->2->3->4<-3<-2<-1
    //逆置完了后
    //   h                 s
    //      h            s
    //         h      s
    //s和h分别往后走判断val是否相同即可
    //整个流程简要概括为：找中间结点、逆置、判断回文（奇数/偶数个结点）
    public boolean chkPalindrome(ListNode A){
        if(A==null){
            return true;//我们这里默认空链表回文
        }
        ListNode F=A;
        ListNode S=A;
        ListNode cur=null;
        //找中间结点
        while(F!=null&&F.next!=null){
            F=F.next.next;
            S=S.next;//F走完S正好走一半
        }
        //反转
        cur=S.next;
        while(cur!=null){
            ListNode curNext=cur.next;
            cur.next=S;
            S=cur;
            cur=curNext;
        }//while结束链表后半部分反转完成,S走到最右边（前半部分还是从前往后走，不用反转）
        //假设原先链表为1->2->3->4->3->2->1（奇数个结点）
        //反转后变为：1->2->3->4<-3<-2<-1

        //假设原先链表1->2->2->1
        //反转后变为：1->2<-2-<1
        //        head                S(S走到最右边了，下面要往回走)
        while(head!=S){
            if(head.val!=S.val){
                return false;
            }
            if(head.next==S){//结点个数为偶数情况
                return true;//比如1 2  2 1，h走到了2，s也走到了2，h.next=s说明其他的已经判断完了
            }
            //如果是结点奇数个，直接用上一个if就行了，两个走到正中间while进不来
            //1 2 3 2 1
            head=head.next;
            S=S.next;
        }
        return true;
    }


    //给定两链表头结点headA，headB，判断两个链表是否相交，
    // 如果相交，返回相交起始结点，如果没有交点，返回null
    //比如给定两个链表A、B
    //情况1
    //A：a->b->c->d
    //B: e->f->b->c->d
    //A和B两链表在b结点开始相交（成Y型，在一结点相交后，后续结点都相同）

    //情况2(错误，原因情况下面)
    //A:a->b->c->d
    //B: e->f->b->g->h
    //A和B两链表在b点相交（成X型，在一结点相交后，后续结点都不同)
    //但这样真的对吗？既然在b点相交，那b.next应该也是一样的，但显然，c！=g，成X型相交不符合逻辑

    //开始写代码，大家又会遇到一个问题，两个链表长度不一定是一样的，
    // 比如上面的A：a->b->c->d      链表长度4
    //         B: e->f->b->c->d   链表长度5
    //怎么让A和B的链表同时走到相同的节点呢？
    //我们先让较长的链表走两个链表结点个数的差值，
    //比如这里A和B链表长度差值为1，我们先让headB先走1步，然后headA和headB一起走就可以保证同时到达相交结点
    //如果题目要求返回后链表保持原始结构，也就是headB和headA不允许动，你定义一个临时变量用headA/B赋值即可

    //测试用例：

    public int Size(ListNode A){
        ListNode cur=A;
        int count=0;
        while(cur!=null){
            count++;
            cur=cur.next;
        }
        return count;
    }
    public  ListNode getIntersectionNode(ListNode headA,ListNode headB){
        if(headA==null||headB==null){//有一个为空，另一个一定无法与它相交
            return null;
        }
        int sz1=Size(headA);//计算一下链表长度
        int sz2=Size(headB);
        ListNode tmpB=headB;
        ListNode tmpA=headA;
        int cz=sz2-sz1;
        if(sz1<=sz2){
            while(cz!=0){//让tmpB先走差值步
                tmpB=tmpB.next;
                cz--;
            }
            while(tmpB!=null){//看看补完差值步后面有没有相交的
                if(tmpA==tmpB){
                    return tmpA;
                }
                tmpA=tmpA.next;
                tmpB=tmpB.next;
            }//遍历结束
            return null;
        }else{
            while((sz1-sz2)!=0){//让tmpA先走差值步
                tmpA= tmpA.next;
            }
            while(tmpA!=null){//看看补完差值步后面有没有相交的
                if(tmpA==tmpB&&tmpA!=null){//防止相同是因为都走到了null
                    return tmpA;
                }
                tmpA=tmpA.next;
                tmpB=tmpB.next;
            }//遍历结束
            return null;
        }
    }

    //判断一个链表是否有环
    //最后一个节点的next不是null，而是前面的某一个节点（不一定是头节点）
    //比如1->2->3->4->5->3//这里的数字不是val，而是节点编号
    //这样的话，第一次走完5,就会无限3-4-5这样走
    public boolean hasCycle(){
        if(head==null){
            return false;
        }
        ListNode fast=head;
        ListNode slow=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            //这里为什么是多走2步而不是多走3步或者其他呢？
            //假如环里就两个结点1->2
            //               1<-2
            //然后我们现在多走3步，3=2+1，也就是多走1循环＋1步，多走一循环相当于在原地，然后两个各加1还是无法相遇
            // 会导致永远不可能相遇
            if(fast==slow){
                break;
            }
        }
        if(fast==null||fast.next==null){
            return false;
        }
        return true;
    }


    //给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null
    public ListNode detectCycle(ListNode head){
        if(head==null){
            return null;
        }
        ListNode fast=head;
        ListNode slow=head;
        while(fast!=null&&fast.next!=null){//判断是否有环
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow){
                break;
            }
        }
        if(fast==null||fast.next==null){
            return null;//走完了，无环
        }
        //已经判断有环，这个时候slow和fast都在相遇点
        fast=head;//开始找环
        while(fast!=slow){
            fast=fast.next;
            slow=slow.next;
        }
        return fast;
    }



    //创建一个带环链表
    public void createLoop(){
        ListNode cur=this.head;
        while(cur.next!=null){
            cur=cur.next;
        }
        cur.next=head.next.next;
    }



    //合并两个有序链表
    public static  ListNode mergeTwoLists(ListNode head1,ListNode head2){
        ListNode newHead=new ListNode(-1);
        ListNode tmp=newHead;
        while(head1!=null&&head2!=null){
            if(head1.val< head2.val){
                tmp.next=head1;
                head1=head1.next;
                tmp=tmp.next;
            }
            else{
                tmp.next=head2;
                head2=head2.next;
                tmp=tmp.next;
            }
        }
        if(head1!=null){
            tmp.next=head1;
        }
        if(head2!=null){
            tmp.next=head2;
        }
        return newHead.next;//newHead是个傀偶节点，真正第一个节点是newHead.next
    }

    //释放链表
    public void clear(){
        while(this.head!=null){
            ListNode curNext=head.next;
            this.head.next=null;
            this.head=curNext;
        }
    }
}
